%----------------------------------------------------------------------------------------
%	CHAPTER 6
%----------------------------------------------------------------------------------------

\chapter{符号表}


第五章所讲的语法分析在整个编译器里处于一个承上启下的作用。所谓“承上”的“上”，是指前端的词法分析，将源程序中的单词识别并翻译为Token序列。语法分析作为过渡阶段，基于Token序列，得到句子的语法树结构。所谓“启下”的“下”，则是指语义分析，根据语法的定义进一步生成中间语言，甚至目标代码。

“语义”在语言学界没有统一的概念。从系统开发角度来讲，在计算机编译程序的过程中，语义是指在基于语法分析结果，执行语义动作。比如，假设目标是将程序翻译为目标代码，语义动作就是生成目标代码的动作；假设目标是统计源代码里Token的数量，语义就是统计数量。换句话说，语义是由开发者（编译器设计者）来定义的。接下来需要对语义进行表示、访问，其中一个非常重要的手段就是符号表，即第六章的内容。   
  
第六章的内容包括符号表的地位和作用、符号表的组织与管理、符号表的结构设计、符号表的构造过程，以及运行时刻存储分配。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\section{符号表的地位和作用}

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection {符号表的定义}
   
符号表是\textbf{标识符}的\textbf{动态语义词典}，属于编译中语义分析的知识库。它的核心目的是组织标识符的查询。其中，符号表面向的对象是标识符，变量、函数名都是标识符。
   
动态语义词典的定义如下：
\begin{itemize} 
\item \textbf{动态}：指标识符表随着编译过程的执行，会发生变化。（也有一些语言在受限的情况下已经预编译好，可以直接运行，则使用静态标识符表）。

例如：递归调用。递归的深度不能预知，故递归操作本身是动态的，跟递归相关的标识符内容也是动态的。
\item \textbf{语义}：指描述标识符所有的信息。

例如：标识符可能是整型变量或浮点型变量，整型或浮点型就是标识符的一种语义。
\item \textbf{词典}：指编译器查询的依据，符号表的目的是让编译器能够快速准确地找到想要查询的标准。
\end{itemize}

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection {标识符的四种语义信息}

\begin{enumerate}
\item {\textbf{名字}}：标识符源码，用作查询关键字。即一个符号，能用来指示标识符，用于唯一标识标识符的身份，便于查询。
\item \textbf{类型}：该标识符的数据类型及其相关信息。
\item \textbf{种类}：该标识符在源程序中的语义角色。
\item \textbf{地址}：与值单元相关的一些信息。地址保存了标识符所对应变量的内容，“值单元”就是存储的地方。	   
\end{enumerate}

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection {符号表的基本功能}

\begin{itemize}	   
\item \textbf{定义和重定义检查}。

定义：可以修改符号表去定义一个变量，例如定义“int A”，要将A填写到符号表里，否则后面不能使用A。

重定义检查：例如在C语言的一个函数里面，不能有两个“int A”，否则会报错“重定义”，报错的原因是在查符号表时发现A已经被定义过了。
\item \textbf{类型匹配校验}

脚本语言分为强数据类型和弱数据类型。C语言、C++等语言是强数据类型，变量类型要先定义好，不能把一个字符串类型赋值给一个整型，编译器在查询符号表的过程中，检查到整型和字符串不匹配，会报错。而Python是弱数据类型，即一个变量不需要定义类型，可以任意赋值，把字符串类型赋值给整型也没有问题。
\item \textbf{数据的越界和溢出检查}

符号表会限制数组的界限，例如生成了一个维度是10的静态数组，如果要访问第11号元素，编译器将会报错“访问非法”。
\item \textbf{值单元存储分配信息}

符号表会定义在哪个位置能找到这个元素。
\item \textbf{函数、过程的参数传递与校验}

举个例子，怎么知道两个函数匹不匹配？调用函数的时候写的方式是否合法？以及类似的问题，都可以通过符号表来解决。
\end{itemize}

符号表实际上是一个逻辑上的概念，并不是物理上制作一个符号表。它贯穿了编译过程中的很多部分，从某种意义上讲，没有符号表，编译器就缺乏了存储的知识，因为编译程序中标识符的定义全部保存在符号表里。
 
%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\section{符号表的组织与管理}

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{符号表的工作原理}
  
符号表的工作有两种操作，一是写，二是读。符号表存储的是标识符对象语义信息，

\begin{itemize}	   
\item 在遇到声明语句，即定义性标识符时，执行写操作，顺着Token指针，将语义信息写入表中，如图\ref{fig:6-1}。

%-----------------------------------------
\begin{figure}[h]
\centering
\input{chapter6/figures/figure-symbol_table_operation}
\caption{符号表操作}
\label{fig:6-1}
\end{figure}
%------------------------------------------

可以理解为\tikz{\node [] (i) {(i , )}; \node [right=0.5em of i] (char) {}; \draw[->, thick]([xshift=-1em,yshift=0em]i.east) -- (char.west);}是一个Token，前面是语法单元，后面是语义信息。将这个Token填到符号表里，从而通过Token指针指向的内容，记录标识符的相关语义信息。
\item 在遇到操作语句，即应用性标识符时，执行读操作，顺着Token指针，读符号表的相应项。

例如定义int A，有C=A+B，把A加B的值赋值给C。目标是查符号表找到A符号所在的位置，用A所在的位置协助访问A的信息。所以同样要把Token的指针指向A所对应的符号表这一项。
\end{itemize}

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{符号表的查询、访问方式}

符号表存储的是所有与用户定义相关的语义信息，在整个编译过程中，对符号表的读写非常频繁，符号表采用的数据结构好坏将直接影响最后编译器的性能。我们学过的数据结构线性表、顺序表、索引表和散列表，都可以采用。具体数据结构的使用不是符号表要介绍的主要内容，本章主要介绍的是符号表承载的语义信息，利用什么样的结构承载这些语义信息。因此本小节提出符号表的查询、访问方式，是为了引起大家注意，在具体使用时还需要具体问题具体分析。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{符号表的维护、管理方式}
  
不同的程序定义符号表的方式不同，在本书中，符号表可以相对片面的理解为：一个源文件有若干个函数组成，每个函数对应一个符号表，此外还有一个全局的公用符号表。
   
符号表的组织方式或管理方式一般是针对语言来说的，实际实现时，往往取决于所属语言的程序结构。就C语言来说，可以在内存设置一定长度的符号表区，对应内存的一段数据，并建立适当的索引机制，访问相应的符号表，符号表区的形式如图\ref{fig:6-2}所示：

%----------------------------------------------------------
\begin{figure}[h]
\centering
\input{chapter6/figures/figure-symbol_table_form}
\caption{符号表区形式}
\label{fig:6-2}
\end{figure}
%----------------------------------------------------------
  
当前函数的所有符号信息，都保存在“现行函数符号表”。如果这个函数被其他函数调用，它上一层函数的符号信息就保存在“\dots”里面，以此类推，第一个函数叫FUNCTION 1，保存在“FUNCTION 1符号表”。所有符号表的最外层是公用符号表，称为全局符号表。

符号表实际上就是按照这种层次化的方式去组织，把下面部分称为局部符号表区，把上面部分称为全局符号表区。可以采用不同的索引机制去索引，保证能访问到所有符号表。
   
%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\section{符号表的结构设计}

%----------------------------------------------------------
\begin{example}
有下列过程函数：

FUNCTION exp ($x$ : REAL; VAR $y$ : INTEGER) : REAL;

CONST pai = 3.14;

TYPE arr = ARRAY[1..5, 1..10] OF INTEGER;

VAR $a$: arr;  $b$, $a$: real;

BEGIN \dots ; $a$[2,5] := 100; $b$ := $z$ + 6; \dots END;

\begin{enumerate}
\item 程序说明：
	
这是一段简单的Pascal语言程序，定义了一个名为exp，返回值为实型的函数，包含两个形参$x$和$y$，$x$是实数（浮点数）类型，是\textbf{赋值形参}，$y$是整型，是\textbf{换名形参}，由关键字VAR声明。函数的代码段从BEGIN开始，一直到END。在函数声明和代码段中间的内容，是一系列声明，包括常量标识符pai=3.14，类型标识符定义整型数组arr，两个变量标识符$a$和$b$，VAR是定义变量的关键字，后面的是变量名。

\item 符号表要回答的问题：

\begin{itemize}
\item 需要进符号表的标识符

exp (函数，附带信息：类型、参数情况和入口地址…), pai (常量), arr (类型), $a$ (下标变量), $b$ (简单变量), \dots
\item 怎样检查出：$a$重定义、$z$无定义以及下标变量？$a$[2,5]的值地址在何处？\dots
\end{itemize}
\textbf{※ 符号表的体系结构设计}

由于标识符的种类不同，导致语义属性也不尽相同。下面提供一个符号表的体系结构如图\ref{fig:6-3}，观察符号表是怎样组织的：

%----------------------------------------------------------
\begin{figure}[h]
\centering
\input{chapter6/figures/figure-symbol_table_architecture}
\caption{符号表体系结构}
\label{fig:6-3}
\end{figure}
%----------------------------------------------------------

符号表 (SYNBL)由词法分析里学到的Token，留有一个指针指向它。符号表有四个属性，可以看成是一个表格。
\begin{itemize}
\item 名字 (NAME)：符号表的名字。
\item 类型 (TYPE)：符号的数学类型。

int、float、char都是数学类型，类型仍然是一个指针，指向一个叫“类型表”的结构。也就是说，符号表是使用一个额外的表来描述类型的。类型表既能表示常见的数据类型，还能记录其它的类型（通过指针指向其他表）。例如“数组表 (ALNFL)”，用来描述数组，在Pascal语言里，数组是一个常见的类型。数组大小，上界和下界，数组的每个元素是什么，都可以通过数组表来定义。此外，类型表还可以指向“结构表 (RINFL)”，C语言里的structure类型即结构体类型，也可以用类型表来描述。类型表可以指向丰富的类型，所有的数据类型都可以通过类型表来定义。
	
\item 种类 (CAT)：变量的种类，按值传递（变量）或按地址传递（函数名）。
\item 地址 (ADDR)：值单元的描述，可简单理解为标识符所存在的物理地址。

地址指向的是内容，例如假设种类是个函数，这时地址指向的是函数表 (PFINFL)，来描述函数的信息；假设定义的是一个常量pai，指向的就是常量表 (CONSL)；还可以指向长度表 (LENL)，记录这个类型多大，占几个字节；最重要的，可能会指向\textbf{活动记录 (VALL)}，活动记录和函数的执行是同时进行的，函数执行过程中会生成相应的活动记录。所有的变量，真正保存的地址就是活动
记录里关于这个变量描述的内容，换句话说，变量的物理存储保存在活动记录里。
\end{itemize}
\end{enumerate}
\label{ex:6-1}
\end{example}
%----------------------------------------------------------
  
下面分别具体介绍符号表各个部分的内容。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{符号表总表 (SYNBL)}

总表结构包括四项内容：

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-SYNBL_architecture}
	\caption{符号表总表 (SYNBL)结构}
	\label{fig:6-4}
\end{figure}
%----------------------------------------------------------
\begin{itemize}
\item NAME (名字)：标识符源码（或内部码）。
\item TYPE (类型)：指针，指向类型表相应项。
\item CAT (种类)：种类编码。

f (函数)，c (常量)，t (类型)，d (域名)，v (常规变量)，vn (换名形参，即地址传递，只需拷贝存储地址)，vf (赋值形参，即值传递，需要将实参拷贝一份到形参存储位置)。
\item ADDR (地址)：指针，根据标识符的种类不同，分别指向函数表PFINFL，常数表CONSL，长度表LENL，活动记录VALL，\dots
\end{itemize}

下面分别具体介绍符号表各个部分的内容。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{类型表 (TYPEL)}

类型表结构包括两项内容：

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-TYPEL_architecture}
	\caption{符号表类型表 (TYPEL)结构}
	\label{fig:6-5}
\end{figure}
%----------------------------------------------------------

\begin{itemize}
\item TVAL (类码)：表示类型的编码。

1. 静态数据类型：包括i (整型)、r (实数型/浮点型)、c (字符型)、b (布尔型)，以及编译器简单预定义好的其他静态数据类型。

2. 复杂数据类型，例如a (数组型)或d (结构体型)，结构体有几个域，每个域是什么，是程序员自己写的，编译器不知道，只能在看到源程序的时候去分析它。从编译的角度来看，它是一个不确定的动态结构，但从执行的角度来看，它又是确定的（这里不需要用静态和动态来区分）。

\item TPOINT (指针)：根据数据类型不同，指向不同的信息表项。指针进一步描述数据的类型。

1. 基本数据类型 (i, r, c, b) —— nul (空指针)。数据类型是预定义好的，不需要进一步描述，指针部分不需要指向任何单元。

2. 数组类型 (a) —— 指向数组表。编译器不知道具体地址，需要根据用户输入的源程序才知道。如果定义了一个数组，指针可能要指向的是数组表。

3. 结构类型 (d) —— 指向结构表。同理数组类型。
\end{itemize}

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{数组表 (AINFL)}

数组表结构包括四项内容：

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-AINFL_architecture}
	\caption{符号表数组表 (AINFL)结构}
	\label{fig:6-6}
\end{figure}
%----------------------------------------------------------
\begin{itemize}
\item LOW (数组的下界)：C语言自动设置为0。
\item UP (数组的上界)：用户定义的最大访问范围。
\item CTP (成分类型指针)：指针，指向该维数组成分类型（在类型表中的信息）。
\item CLEN (成分类型长度)：成分类型的数据所占值单元的个数（假定：值单元个数依字长为单位计算）。
\end{itemize}

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{结构表 (RINFL)}

一个结构体会包括若干项，称之为域，每个域占表中的一个记录，指示结构体的每一项都是什么类型。结构表结构包括三项内容：

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-RINFL_architecture}
	\caption{符号表结构表 (RINFL)结构}
	\label{fig:6-7}
\end{figure}
%----------------------------------------------------------
\begin{itemize}
\item ID (结构的域名)：每个域的名字。
\item OFF (区距)：是$id_{k}$的值单元首地址相对于所在记录值区区头位置。

计算公式如下：

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-off_alculation_formula}
	\label{fig:6-8}
\end{figure}
%----------------------------------------------------------

公式说明：第1个域的偏移是0，即区距是0。第2个域的区距将第1个域所对应的区距加上第1个域所对应变量的长度。以此类推，第n个域的区距就是域n-1的起始地址再加上第n-1个域对应变量的长度，称为第n个域的偏移。

\item TP (域成分类型指针)：指针，指向$id_{k}$域成分类型（在类型表中的信息）。

思考：为什么类型要用一个复杂的类型表去表示？

1. 重用：定义数组类型之后，这个类型可以定义很多变量，不需要每定义一次变量就把类型重新定义一遍。

2. 复杂数据类型，需要对类型本身进行复杂地描述。如果全是预定义类型，一个编码就足够，但是复杂的数据类型用简单的类型无法描述，在设计数据结构时，就不能统一用一个表来做，要分出一个数据类型来单独描述。这也是一种编程的常规的习惯，由于描述的对象很复杂，不是一个静态的东西，因此需要一个动态的内容去描述。
\end{itemize}

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{函数表 (PFINFL)——过程或函数语义信息}

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-PFINFL_architecture}
	\caption{符号表函数表 (PFINFL)结构}
	\label{fig:6-9}
\end{figure}
%----------------------------------------------------------

\begin{itemize}
\item LEVEL (层次号)：该过函静态层次嵌套号，用来表示函数的位置（并非递归的层次）。
\item OFF (区距)：该过函自身数据区起始单元相对该过函值区区头位置。
\item FN (参数个数)：该过函的形式参数的个数（可以没有）。
\item PARAM (参数表)：指针，指向形参表（描述每个参数的内容）。形参是函数非常重要的语义信息，且数量可能较多，因此构建形参表，并以指针形式由PARAM指向形参表。
\item ENTRY (入口地址)：该函数目标程序首地址（运行时填写）。
\end{itemize}

对LEVEL、OFF进行说明：函数包括数据对象以及对对象进行的操作，这两部分内容都需要载入内存，操作部分不属于本章讨论范围。下面针对数据对象部分，进一步讨论。

编译器处理一个函数的所有数据对象时，载入内存一定是连续存储的。设计的函数是静态的，函数被载入内存一次就产生一次活动，在这次活动中处理的数据对象所在区域，被存储在活动记录中。活动记录会存储形参变量、局部变量、临时变量。

以$x=x+10$为例，编译器将该语句分解为计算和赋值两步，开始计算得到$x+10$的结果，即为临时变量，存放中间结果。除变量数据之外，活动记录还需要记录管理数据，如函数嵌套调用时的返回地址存储，断点保存等。管理数据从区头开始存放，占据一定空间，变量数据区起始单元相对区头的位置，记为区距OFF。层次号LEVEL用于处理变量作用域问题，以C语言程序段为例，主函数中定义了$x, y$，中间某一段过程中调用的$x$来自该段程序中定义的$x$，调用的$y$来自前面定义的$y$，我们可以通过层次号区分不同作用域的变量。如图所示，将前面的int $x$, $y$;所在作用域定为L层，则中间段就属于L+1层，从逻辑上来说，可以将$x$进行区分，开始定义的$x$是第L层的，中间段的$x$是L+1层的。在C语言中，函数不可嵌套定义，而在pascal语言中，可以在函数内部定义子函数，在这种情况下，LEVEL的标识尤为重要。LEVEL表示该过程或函数静态层次嵌套号，根据写好的程序进行判断，不随运行时刻而改变。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{其他表 (\dots)}

\begin{itemize}
\item 常量表 (CONSL)：存放相应常量的初值，仅有一个域。对于字符常量、字符串常量、实型常量、整型常量等这些不同类型的常量，分别列表。
\item 长度表 (LENL)：存放相应数据类型所占值单元个数，仅有一个域。
\item 活动记录表 (VALL)：一个函数（或过程）虚拟的值单元存储分配表；是函数（或过程）所定义的数据，在运行时刻的内存存储映像。
\end{itemize}

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\section{符号表的构造过程示例}

%----------------------------------------------------------
\begin{example}
根据函数构造符号表:

FUNCTION exp ($x$ : REAL; VAR $y$ : INTEGER) : REAL;

CONST pai = 3.14;

TYPE arr = ARRAY[1..5, 1..10] OF INTEGER;

VAR $a$: arr;  $b$, $a$: real;

BEGIN \dots ; $a$[2,5] := 100; $b$ := $z$ + 6; \dots END;

填表过程如图\ref{fig:6-10}：

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-filling_process_of_symbol_table1}
	\caption{符号表填写过程}
	\label{fig:6-10}
\end{figure}
%----------------------------------------------------------

\begin{enumerate}

\item exp (函数)

\begin{itemize}
\item 填符号表SYNBL：NAME域填函数名字exp，TYP域填函数的返回值类型rtp（实数型），CAT域填写函数的种类f（函数），ADDR域指向函数表。

\textbf{说明}：rtp是指针，指向TYPEL中的r项，此处是为了节省画图空间，简化为这样。

\item 填函数表PFINFL：没有完整的程序不知道函数表的层次号，编译时才知道，所以暂时不填LEVEL域，OFF域指向exp返回值所存的内容，即v1的地址，FN域填函数的变量个数2，ENTRY域填函数入口地址ENT，PARAM域指向形参表，暂时不填。
\end{itemize}

\item $x$ (变量)

\begin{itemize}
\item 填符号表SYNBL：函数有两个变量，在符号表中继续填$x$的相关内容，NAME域填变量名字$x$，TYP域填变量类型rtp（实数型，指向类型表的r项），CAT域填写变量种类vf（赋值形参，按值传递的参数）。$x$值存在活动记录VALL中exp值的下一个位置（VALL中的地址从下至上依次增大），$x$的起始地址记为v2，将其填在ADDR域内（实际上v2是一个指针，指向VALL中v2的内容，此处为了记录简洁，没有画出指针）。
\item 填形参表PARAM：根据$x$的名字、类型、种类、地址，填写NAME、TYP、CAT、ADDR四项内容。

\textbf{思考}：为什么在符号表中填完$x$，还要在参数表中再填一遍？两项内容是完全相同的。
\end{itemize}

\item $y$ (变量)

\begin{itemize}
\item 填符号表SYNBL：在符号表中继续填$y$的相关内容，NAME域填变量名字$y$，TYP域填变量类型itp（整型，指向类型表的i项），CAT域填写变量种类vn（换名形参，按地址传递的参数）。$y$值存在活动记录VALL中$x$值的下一个位置，起始地址记为v3，将其填在ADDR域内。

\textbf{思考}：$y$是按地址传递的参数，那么VALL中变量$y$中存的内容是什么？是$y$所指向的值还是$y$的地址？

\textbf{答}：保存的是$y$的地址，这里有一个重要的概念——解引用。按地址传递的好处是可以直接修改原始变量的内容；坏处是多了一次解引用，解释地址指向的内容，多了一次跳转，导致速度变慢。

\item 填形参表PARAM：根据$y$的名字、类型、种类、地址，填写NAME、TYP、CAT、ADDR四项内容。
\end{itemize}

\item pai (常量)

\begin{itemize}
\item 填符号表SYNBL：在符号表中继续填pai的相关内容，NAME域填常量名字pai，TYP域填常量类型rtp（实数型，指向类型表的r项），CAT域填写常量种类c。ADDR域指向常量表CONSL。
\item 填常量表CONSL：填入3.14。
\end{itemize}

\item arr (数组类型)

\begin{itemize}
\item 填符号表SYNBL：在符号表中继续填arr的相关内容，NAME域填名字arr，TYP域指向数组的定义——类型表。
\item 填类型表TYPEL：没有数组的定义，要新增。TVAL域填类码a，TPOINT域指向数组表。
\item 填数组表ALNFL：LOW域填数组的下界1（Pascal语言从1开始），UP域填数组的上界5，CTP域指向类型表，表示每个单元的类型，仍然是数组类型a（嵌套）。由于该数组类型没有被定义过，所以类型表再次新增一行。CLEN域填值单元的长度10（填完ALNFL之后得到，根据数组范围可计算整个数组长度为50）。
\item 填类型表TYPEL：TVAL域填类码a（与上一个数组类型的定义不同），TPOINT域指向数组表。
\item 填数组表ALNFL：LOW域填数组的下界1，UP域填数组的上界10，CTP域指向类型表，此处填itp（整型，指向类型表的i项），CLEN域填值单元的长度1。此时，反推上一个数组单元的长度为10。
\item 填符号表SYNBL：CAT域填写数组种类t（类型，可以用作定义其他变量的数据类型）。ADDR域指向长度表。
\item 填长度表CONSL：填入50。
\end{itemize}

\item $a$ (变量)

填符号表SYNBL：在符号表中继续填$a$的相关内容，NAME域填变量名字$a$，TYP域指向类型表中arr定义的数组类型a，CAT域填写变量种类v。$a$值存在活动记录VALL中，起始地址记为v4，将其填在ADDR域内（占50个单元）。

VALL中链接表的作用：静态数据类型直接放在底部，复杂数据类型编译器不知道内容，需要指令分析所以放在链接表上面。

\item $b$ (变量)

填符号表SYNBL：在符号表中继续填$b$的相关内容，NAME域填变量名字$b$，TYP域填变量类型rtp（实数型，指向类型表的r项），CAT域填写变量种类v。$b$值存在活动记录VALL中，起始地址记为v5，将其填在ADDR域内。

\end{enumerate}

\textbf{※强调}：如果种类是类型，指向的是长度表，因为要知道这个类型占多少空间；如果种类是变量，只需要知道它的物理地址，指向地址。

\label{ex:6-2}
\end{example}
%----------------------------------------------------------

%----------------------------------------------------------
\begin{example}
根据类型说明填写符号表

TYPE arr = ARRAY [1..10] 0F ARRAY [1..5] 0F INTEGER;

设：实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。

i，r，c，b是不同的项，它们的指针都为空。该例主要介绍二维数组如何存储，填表过程如图\ref{fig:6-11}:

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-filling_process_of_symbol_table2}
	\caption{符号表填写过程}
	\label{fig:6-11}
	\end{figure}
%----------------------------------------------------------

\begin{itemize}
\item 填符号表SYNBL：NAME域填数组名字arr，TYP域指向类型表，arr是一个二维数组（数组嵌套数组）。
\item 填类型表TYPEL：TVAL域填类码a，TPOINT域指向数组表。
\item 填数组表ALNFL：LOW域填数组的下界1，UP域填数组的上界10，CTP域指向类型表，仍然是数组类型a（嵌套），类型表再次新增一行。CLEN域填值单元的长度20（填完ALNFL之后得到，根据数组范围可计算整个数组长度为200）。
\item 填类型表TYPEL：TVAL域填新的类码a，TPOINT域指向数组表。
\item 填数组表ALNFL：LOW域填数组的下界1，UP域填数组的上界5，CTP域填itp（整型，指向类型表的i项），CLEN域填值单元的长度4。此时，反推上一个数组单元的长度为20。
\item 填符号表SYNBL：CAT域填写数组种类t（类型，可以用作定义其他变量的数据类型）。ADDR域指向长度表。
\item 填长度表CONSL：填入200。
\end{itemize}

\label{ex:6-3}
\end{example}
%----------------------------------------------------------

%----------------------------------------------------------
\begin{example}
根据类型说明填写符号表

TYPE rec = RECORD

$u$: INTEGER;

$v$: ARRAY[1..10] OF BOOLEAN;

$r$: RECORD $x, y$ : REAL END

END;

设：实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。

一个记录可以理解为结构体，由3部分组成：第一个域$u$ ——整型；第二个域$v$ ——10维的布尔类型数组；第三个域$r$ ——结构体，由两个域$x$和$y$构成，都是实数类型。

复杂的结构在符号表里的表示过程如图\ref{fig:6-12}：

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-filling_process_of_symbol_table3}
	\caption{符号表填写过程}
	\label{fig:6-12}
\end{figure}
%----------------------------------------------------------

\begin{itemize}
\item 填符号表SYNBL：NAME域填记录名字rec，TYP域指向类型表，新增一个结构体类型d（跳转到TYPEL），CAT域填写结构体种类t，ADDR域指向长度表。
\item 填类型表TYPEL：若TVAL域填类码d，TPOINT域指向结构表（跳转到RLNFL）；若TVAL域填类码a，TPOINT域指向数组表（跳转到ALNFL）。
\item 填结构表RLNFL：

1. 第一条记录：ID域填第一个结构体的第一个域名$u$，OFF域填区距0（因为是第一个域），TP域填itp（整型，指向类型表的i项）。同时在符号表中描述$u$，NAME域填$u$，TYP域填itp，CAT域填结构类型d，ADDR域指向的长度表填4。

2. 第二条记录：ID域填第一个结构体的第二个域名$v$，OFF域填区距4（第一个域的区距+第一个域的长度），TP域指向类型表，新增一个数组类型a（跳转到TYPEL）。同时在符号表中描述$v$，NAME域填$v$，TYP域指向类型表中新添加的数组类型a，CAT域填结构类型d，ADDR域指向的长度表填10。

3. 第三条记录：ID域填第一个结构体的第三个域名$r$（仍是一个结构体），OFF域填区距14（第二个域的区距+第二个域的长度），TP域指向类型表，新增一个结构类型d（跳转到TYPEL）。同时在符号表中描述$r$，NAME域填$r$，TYP域指向类型表中新添加的数组类型d，CAT域填结构类型d，ADDR域指向长度表。

4. 第四条记录：ID域填第二个结构体的第一个域名$x$，OFF域填区距0（因为$x$是新纪录的第一个域），TP域填rtp（实数型，指向类型表的r项）。同时在符号表中描述$x$，NAME域填$x$，TYP域填rtp，CAT域填结构类型d，ADDR域指向的长度表填8。

5. 第五条记录：ID域填第二个结构体的第一个域名$y$，OFF域填区距8（第一个域的区距+第一个域的长度），TP域填rtp（实数型，指向类型表的r项）。同时在符号表中描述$y$，NAME域填$y$，TYP域填rtp，CAT域填结构类型d，ADDR域指向的长度表填8。

\item 填数组表ALNFL：LOW域填数组的下界1，UP域填数组的上界10，CTP域填btp（布尔型，指向类型表的b项），CLEN域填值单元的长度1。此时，反推数组的长度为10。
\item 填长度表CONSL：完善r的长度$=16(x+y)$，rec的长度$=30(u+v+r)$。
\end{itemize}

\label{ex:6-4}
\end{example}
%----------------------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\section{运行时刻存储分配}

本节介绍\textbf{标识符}标识符变量的\textbf{地址分配}与对它们的访问，主要讲解类码为v的标识符地址分配问题。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{标识符值单元分配}

一个变量保存的位置，在C++语言里用new就可以得到，但是需要注意，程序运行是有环境的，不能单独写一个new语句来运行，要放在一段程序里，具体来说是放在一个函数里去执行。这个问题衍生出一个思考，分配new的时候，是在一个什么样的条件下去分配？在函数内部可以做new操作，外部也行，因为main函数也是一个函数。

对于值单元的分配，一般有两种策略。

\begin{enumerate}
\item 静态分配:

在\textbf{编译阶段}即可完成真实的地址分配。在编译时对所有数据对象分配固定的存储单元，且在运行时始终保持不变。
\begin{itemize}
\item 优点：程序编译之后、执行之前，就知道每个变量所存的位置和大小。静态分配不需要计算变量的存储位置，可以提高程序执行的效率。
\item 缺点：如程序递归调用时，不能做到静态分配。递归的层数由用户输入的变量决定，递归函数每个变量的存储位置不能确定，这种情况下采用动态分配。
\end{itemize}

\item 动态分配:

在\textbf{运行时刻}进行的值单元分配，即动态地决定变量所存储的位置和大小，在编译时只能进行相对地址分配。

\begin{itemize}
\item 栈式动态分配：栈常用于先进后出的操作。
\item 堆式动态分配：堆常用于维护一个有序的表，排序、top-k等可以用堆加速操作过程。
\end{itemize}

\textbf{注}：值单元分配是以过程函数为单位的，每个过程函数有其自身的活动记录。“过程”在Pascal语言里可以简单地理解为没有返回值的函数。
\end{enumerate}

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{活动记录}

首先介绍三个基本概念：

\begin{enumerate}
\item 过程：一个可执行模块，过程或函数，通常完成特定的功能。一个过程在编译器里指一段有独立功能的程序，可以完成一个函数或者一个Pascal过程，也可以称为一个函数。
\item 活动：过函的一次执行。每执行一次过程函数体，则产生该过函的一个活动。
\item 活动记录：一个有结构的连续存储块。用来存储过函一次执行中所需要的的信息。所谓结构，是指定义了管理数据、形参、局部变量等的位置结构，可视作一种数据结构。
\end{enumerate}

三者关系：过程是一个抽象的概念，不对应函数具体的执行；活动是这个抽象概念的一次具体实现过程；活动记录是伴随着活动被定义的概念，一个活动记录用来记录一个活动所需要或产生的信息。

注意：

\begin{itemize}
\item 活动记录并不是针对某一个函数，而是针对这个函数的一次执行。更准确地说，是运行时所产生的一个记录，而不运行就没有活动或活动记录，只有过程。
\item 活动记录仅是一种存储映像，编译程序所进行的运行时刻存储分配是在符号表中进行的，符号表中分配的变量就存储在活动记录里。
\item 如果不支持可变数据结构（如动态数组，需要动态存储），活动记录的体积是可以在编译时确定的。
\end{itemize}

活动记录结构如图\ref{fig:6-13}所示：

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-VALL_architecture}
	\caption{活动记录结构}
	\label{fig:6-13}
\end{figure}
%----------------------------------------------------------

\begin{enumerate}
\item 连接数据区

\begin{itemize}
\item 返回地址：保存断点地址，返回主控程序时继续执行的位置。（断点地址：函数被调用时的返回地址，是汇编语言执行的地址，而不是活动记录的返回地址。）
\item 动态链：指向调用该过程的主调程序的活动记录的指针。（直接外层：与层次有关，如果是在第3层调用，直接外层就是第2层。）
\item 静态链：指向静态直接外层活动记录的指针。
\end{itemize}

\item 形式单元

用来存放实参的值或地址。

\item 局部数据区

用来存放局部变量、内情向量、临时单元。内情向量存放计算过程中的一些相关参数；临时单元存放运算过程中的中间结果（在生成中间代码时生成的非用户定义的临时变量）。

\item 栈指针

\begin{itemize}
\item SP：指向现行过程活动记录的起点，即第一个单元。
\item TOP：指向（已占用）栈顶单元，即活动记录的最后一个单元。
\end{itemize}

用SP和TOP就可以确定活动记录所在的物理存储的区间。
\end{enumerate}

%----------------------------------------------------------
\begin{example}
动态链、静态链

动态是指运行过程中，而静态是指编写程序时。

\begin{itemize}
\item 动态链与程序调用有关。

M程序调用N子程序的活动记录栈结构如下图，当M程序载入内存时，两个指针指向M活动记录的起始位置和终止位置，定义了当前可操作的数据区。当N子程序载入内存时，N活动记录进入活动记录栈，这两个指针移动到指向N活动记录的起始位置和终止位置，表示当前运行函数为n。这两个指针限定了当前可操作的数据区，即当前运行函数的数据区。

当N运行结束返回M时，N活动记录弹栈，两个指针又重新指向M活动记录的起始位置和终止位置。为了获知M活动记录的位置，在n活动记录中开辟一个域，当N活动记录压栈时，M程序将自身活动记录首地址放入该域中，指针指向M活动记录首地址，该指针就是动态链。

\item 静态链与程序设计相关。

Pascal语言允许嵌套定义函数，例如在函数P中嵌套定义了函数M和函数N，在函数M中又嵌套定义了函数Q。换言之，Q子程序可以访问M的数据，也可以访问P的数据，但是不能访问N的数据，而M可以调用N，N也可以调用M。此处涉及函数作用域的问题，内层的函数可以访问外层的、嵌套的外层的数据。例如在函数P中定义了变量$x$，在函数Q中存在$x=10$; 语句，在活动记录中结构如下图所示。函数P的活动记录压栈，包含$x$的信息，不断调用，将Q压栈，此时动态链指向Q活动记录的起始位置和终止位置，但是$x$不在Q的活动记录内，无法根据动态链找到$x$的位置。Q访问$x$需要获知P活动记录的首地址，再根据变量$x$的区距找到$x$。函数Q保存静态定义的外层M，再外层P等所有外层在内存中最新活动记录的首地址信息，就可以进行上述访问操作，这就是静态链。
\end{itemize}

此类变量作用域的问题，与静态设计相关，需要通过静态链解决。静态链可以指向静态直接外层活动记录的首地址，也可以通过多步跳转访问各个外层函数的数据。

\label{ex:6-5}
\end{example}
%----------------------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{简单的栈式存储分配}

以C语言为例：没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用。

%----------------------------------------------------------
\begin{example}
C语言过程调用关系：Main() -> Q() -> R()

\begin{enumerate}
\item C语言程序的存储组织

活动记录栈状态如图\ref{fig:6-14}，从下往上，地址由小到大。由于是栈式存储分配，后调用的函数存储在栈顶。当R()执行结束后弹栈，再执行Q()，以此类推。下图中当前运行函数为R，可操作数据区由指针SP和TOP进行限定。SP和TOP分别指向当前活动记录的首尾地址，即R的第一个单元和最后一个单元。

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-C_VALL_1}
	\caption{C语言调用过程VALL-1}
	\label{fig:6-14}
\end{figure}
%----------------------------------------------------------

\item C的活动记录

如图\ref{fig:6-15}所示，将参数个数加入活动记录中，该形式支持被调函数完成实参到形参的传递。Old SP指向上一个调用函数的过程所对应活动记录的首地址，由动态链完成。C语言中函数不可嵌套定义，因此活动记录中只有动态链，没有静态链。

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-C_VALL_2}
	\caption{C语言调用过程VALL-2}
	\label{fig:6-15}
\end{figure}
%----------------------------------------------------------

\item C语言的过程调用与返回

(1) 过程调用

\begin{itemize}
\item 过程调用的四元式序列

\begin{tabular}{p{2em}p{3em}*{2}{p{0.5em}}}
(param,&entry($t_1$),&\_\_,&\_\_) \\
&\dots\dots \\
(param,&entry($t_n$),&\_\_,&\_\_)\\
(call,&entry(P),&\enspace n,&\_\_)	
\end{tabular}

四元式的第一个元素是操作的运算符或函数，第二、三个元素是操作对象，第四个元素是结果；(param, entry($t_1$), \_\_, \_\_) \dots\dots (param, entry($t_n$), \_\_, \_\_)表示对变量$t_1$到$t_n$，用param进行操作，得到的结果保存在对应四元式的最后一个位置\_\_；(call, entry(P), n, \_\_)表示调用P函数。

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-quad_of_calling_function}
	\caption{调用函数过程四元式序列}
	\label{fig:6-16}
\end{figure}
%----------------------------------------------------------

图\ref{fig:6-16} 四元式序列描述调用函数的过程。$t_1$到$t_n$表示函数的实参地址，entry(P)表示调用函数的入口地址，参数个数是n。

\item 对应的目标指令

四元式：(param, entry($t_i$), \_\_, \_\_)

作用：现有主调过程的活动记录，此时还未执行到函数P对应的活动记录。构建一个过程P所对应的活动记录，(param, entry($t_i$), \_\_, \_\_)将$t_i$写入子程序P活动记录中的形参区对应的位置。

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-C_VALL_3}
	\caption{C语言调用过程VALL-3}
	\label{fig:6-17}
\end{figure}
%----------------------------------------------------------

对应指令：

$(i+3)[\text{TOP}] := \text{entry}(t_i).\text{Addr}$ \qquad//将$t_i$地址填到活动记录的形参区去

以上语句表示：在TOP地址之上第$i+3$个单元，保存变量$t_i$的地址。$(i+3)$表示在TOP地址之上增加$i+3$个偏移量，因为形参区的第一个单元与TOP之间相差3个单元，所以$i+3$可以索引到当前所要访问的形参编号。

四元式：(call, entry(P), n, \_\_)

作用：表示要执行过程P，但此时P活动记录里的一些必要信息还没有填写。(call, entry(P), n, \_\_)填写Old SP和参数个数n。

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-C_VALL_4}
	\caption{C语言调用过程VALL-4}
	\label{fig:6-18}
\end{figure}
%----------------------------------------------------------

对应指令：

\begin{tabular}{ll}
$1[\text{TOP}] := \text{SP}$ & \qquad//保护现行SP \\

$3[\text{TOP}] := \text{n}$ & \qquad//传递参数个数 \\

$\text{JSP} \qquad \text{P}$
\end{tabular}

以上语句表示：Old SP将上一个过程即主调过程的SP（指向主调过程的首地址），填写在TOP地址之上1个偏移量的位置。参数个数n填写在TOP地址之上3个偏移量的位置。最后跳转到P，指的是汇编语言里真正要执行的函数过程的首地址，不是活动记录的首地址。

\item  子过程P需完成自己的工作：定义自己的活动记录

此时，SP和TOP还未指向当前要执行的子过程P的活动记录，需要分别指向子过程P的起始地址和终止地址，还需要填写P执行之后的返回地址。（假设P活动记录长度为L）

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-C_VALL_5}
	\caption{C语言调用过程VALL-5}
	\label{fig:6-19}
\end{figure}
%----------------------------------------------------------

对应指令：

\begin{tabular}{ll}
$\text{SP} := \text{TOP}+1$ &\qquad//定义过程P的SP\\

$1[\text{SP}] := \text{返回地址}$ &\qquad//保护返回地址\\

$\text{TOP} := \text{TOP}+\text{L}$ &\qquad//定义新TOP
\end{tabular}

\end{itemize}

(2) 过程返回

\begin{itemize}
	
\item 过程返回的四元式：(ret, \_\_, \_\_, \_\_)

ret指令表示返回。

\item 对应的目标指令：

此时，子过程P执行结束，返回主调过程，需要将TOP和SP重新指向主调过程的起始和终止位置：TOP移动到主调过程的最后一个单元，SP的前一个单元；SP移动到P活动记录中Old SP记录的地址，即主调过程活动记录的SP。最后根据子过程P的返回地址，跳转回调用位置的下一条语句。（注：返回地址表示函数真实执行的位置，活动记录中记录函数里所存储的量的位置。）

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-C_VALL_6}
	\caption{C语言调用过程VALL-6}
	\label{fig:6-20}
\end{figure}
%----------------------------------------------------------

对应指令：

\begin{tabular}{ll}
$\text{TOP} := \text{SP}-1$ &\qquad//恢复TOP\\
$\text{SP} := 0[\text{SP}]$ &\qquad//恢复SP\\
$\text{X} := 2[\text{TOP}]$ &\qquad//取返回地址，X为某一变址器\\
$\text{UJ} \qquad 0[\text{X}]$    &\qquad//按X中的返回地址实行变址转移\\
\end{tabular}
\end{itemize}

\end{enumerate}

\label{ex:6-6}
\end{example}
%----------------------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{嵌套过程语言的栈式存储分配}

\begin{enumerate}
\item 标识符的作用域

(1)	过程嵌套的一个关键问题：\textbf{标识符的作用域问题}

标识符的作用范围往往与它所处的过程相关，也就是说，同一个标识符，在不同的程序段里，代表不同的对象，具有不同的性质，因此要分配不同的存储空间。

(2)	标识符的有效范围：\textbf{服从最小作用域原理}

\begin{itemize}
\item 在外层未定义，而在内层定义的，服从内层定义；
\item 在外层已定义，而在内层未定义的，服从外层定义；
\item 在外层已定义，而在内层也定义的，在外层服从外层定义，在内层服从内层定义（就近原则）。
\end{itemize}

\item 活动记录

(1)	问题的提出：

过程Q可能会引用到它的\textbf{任意外层}过程的最新活动记录中的某些数据，该如何存储？

(2)	解决问题的思想：

为了在活动记录中查找这些非局部名字所对应的存储空间，过程Q运行时必须设法跟踪它的\textbf{所有外层}过程的最新活动记录的地址。

(3)	解决方案：

活动记录中增加\textbf{静态链}如图\ref{fig:6-21}的最新活动记录的首地址。

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-VALL_with_static_chain}
	\caption{添加静态链的活动记录}
	\label{fig:6-21}
\end{figure}
%----------------------------------------------------------

\item 嵌套层次显示表（display）和活动记录结构
%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-VALL_with_display}
	\caption{添加嵌套层次显示表的活动记录}
	\label{fig:6-22}
\end{figure}
%----------------------------------------------------------

(1)	连接数据区：0~2

\begin{itemize}
\item Old SP——主调过程的活动记录首地址
\item 全局display地址——主调过程的显示区表首址，用于访问当前活动记录所有外层的活动记录信息
\end{itemize}

(2)	参数个数：3

(3)	形参值单元区：入口为4

\begin{itemize}
\item 换名形参(vn)——分配2个单元（地址传递）
\item 赋值形参(vf)——按相应类型长度分配
\end{itemize}

(4)	显示区表（display）：指向外层活动记录的指针，占I+1个单元

I为层次号，包含直接外层嵌套的I个过程的活动记录的首地址，再加上本过程的活动记录首地址

(5)	局部变量区：入口为off + I + 2

\begin{itemize}
\item off为形参区最后一个值单元地址
\item 局部变量值单元按相应类型长度分配地址
\item 类型标识符、常量标识符等不分配值单元；常量放在常数表，跟函数表用没有关系
\end{itemize}

(6)	临时变量区：

编译系统定义的变量，按局部变量值单元分配原则分配地址

\item Display表的建立

设过程调用关系为Q() -> R()，且R()的层次号为I，则Q与R的display表的关系如图\ref{fig:6-23}：

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-relation_between_displayQ&R}
	\caption{Q与R的display表关系}
	\label{fig:6-23}
\end{figure}
%----------------------------------------------------------

R的活动记录：

\begin{itemize}
\item Old SP：指向Q活动记录的首地址。
\item 全局Display地址：指向Q的显示区表首地址。让当前活动记录能访问到所有外层的活动记录，外层的活动记录存储在Q的活动记录的显示区表里。
\item 显示区表(Display)：长度为I+1个单元。从Q的显示区表拷贝I个单元（第I层拷贝I个），并将自身活动记录首地址写入显示区表的第I+1个单元。
\end{itemize}


%----------------------------------------------------------
\begin{example}
设有Pascal程序片段如图\ref{fig:6-24}：

这是Pascal中一个完整程序形式，函数（或过程）是用program（或procedure）定义的。P是主程序，除了定义两个变量外，还定义了两个子程序，分别是Q和S，Q又定义了自己的内部函数为R。因此该程序片段中，P是0层，Q和S是1层，R是2层。

主控程序的代码在最后的begin到end，调用了函数S，S代码段中，调用了函数Q，Q代码段中调用了函数R。因此，整个过程的调用关系为P->S->Q->R。

根据调用关系，我们可以判断活动记录栈的大致形式如下。下面对P、S、Q、R的活动记录进一步说明，模拟运行时的活动记录。图\ref{fig:6-25}是整个调用过程的内存映像。

\begin{itemize}
\item P的活动记录：

P为0层，由于P是系统调用的，Old SP为0，返回地址的值运行时存放断点地址，全局Display地址为0，参数个数为0，Display表长度为1，存放自身活动记录首地址0。根据函数定义填写局部变量为$a$和$x$，用“$a$-(0,5) ”表示变量$a$的层次号为0，偏移量为5。

\item S的活动记录：

P调用S，S的活动记录载入内存。S的Old SP指向P的活动记录首地址0，返回地址内容运行时进行填写，全局Display指向P的Display表首地址4，参数个数为0。S是1层， Display表长度为2，先拷贝P的Display表0，再写入自身活动记录首地址13，根据函数定义填写局部变量$c$和$i$。

\item Q的活动记录：

S调用Q，Q的活动记录载入内存。Q的Old SP指向S的活动记录首地址13，返回地址内容运行时进行填写，全局Display指向S的Display表首地址17，参数个数为1，接着存放形参$b$。Q也是1层，Display表长度为2，拷贝S的Display表中前1个单元内容0，再写入自身活动记录首地址27，根据函数定义填写局部变量$i$。

\item R的活动记录：

Q调用R，R的活动记录载入内存。R的Old SP指向Q的活动记录首地址27，返回地址内容运行时进行填写，全局Display指向Q的Display表首地址35，参数个数为2，依据参数类型进行存放形参$u$和$v$。R是2层，Display表长度为3，拷贝Q的Display表中前2个单元0和27，再放入自身活动记录首地址41，然后根据函数定义填写局部变量$c$和$d$。

%----------------------------------------------------------
\begin{figure}[h]
	\centering
	\input{chapter6/figures/figure-pascal_program}
	\caption{Pascal程序片段}
	\label{fig:6-24}
	\end{figure}
%----------------------------------------------------------

\end{itemize}

%----------------------------------------------------------
\begin{figure}[h]
\centering
\input{chapter6/figures/figure-calling_process_of_VALL_stack}
\caption{活动记录栈调用过程}
\label{fig:6-25}
\end{figure}
%----------------------------------------------------------

\label{ex:6-7}
\end{example}
%----------------------------------------------------------

\item 值单元的地址分配
值单元分配是依据活动记录的结构，在符号表中进行的。

%----------------------------------------------------------
\begin{example}
Pascal程序片段如下，P1所在层level=2，试给出符号表组织及值单元分配情况。图\ref{fig:6-26}左侧是符号表的内容，右侧紫色框是活动记录。

设:(1)实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元

(2)换名形参vn分配2个单元，赋值形参vf按相应类型长度分配

PROCEDURE P1( $x$: REAL; VAR $y$: BOOLEAN );

CONST pai $=$ 3.14;

TYPE arr $=$ ARRAY [1..10] OF INTEGER;

VAR $m$: INTEGER;

\indent $a$ : arr;

\indent $l$ : REAL;

FUNCTION F1( $z$ : REAL; $k$ : INTEGER ): REAL;

\indent BEGIN \dots\dots END;

\dots\dots;

BEGIN

\indent \dots\dots;

END;

%----------------------------------------------------------
\begin{figure}[h]
\centering
\input{chapter6/figures/figure-filling_process_of_symbol_table_and_VALL}
\caption{符号表+活动记录填写过程}
\label{fig:6-26}
\end{figure}
%----------------------------------------------------------

\label{ex:6-8}
\end{example}
%----------------------------------------------------------

该程序片段定义了一个过程P1，层次号为3。包括1个常量标识符，1个类型标识符，3个局部变量，1个内部函数。P1定义了F1，F1的层次号为4。

符号表组织及值单元分配情况过程：

(1) P1 (过程)

\begin{itemize}
\item 填符号表SYNBL：NAME域填过程名字P1，TYP域没有返回值不填，CAT域填写函数的种类p (过程)，ADDR域指向函数表。
\item 填函数表PFINFL：LEVEL域填函数的层次号3，OFF域填区距3，FN域填函数的变量个数2，ENTRY域填函数入口物理地址Entry，PARAM域指向形参表。
\item 填形参表PARAM：根据$x$和$y$的名字、类型、种类、地址，填写NAME、TYP、CAT、ADDR四项内容。其中ADDR内容在填完VALL之后，填入变量的层次号和偏移，$x$对应(3,4)，$y$对应(3,12)。填好形参表之后，在符号表中填入变量$x$和$y$的相关信息（与形参表中内容一致）。
\item 填活动记录VALL：参数个数为2；形式单元填$x$，实型占8个单元，偏移量为4-11，填$y$，布尔型占1个单元，偏移量为12-13。Display表长度为4。
\end{itemize}

(2) pai (常量)

\begin{itemize}
\item 填符号表SYNBL：在符号表中继续填pai的相关内容，NAME域填常量名字pai，TYP域填常量类型rtp（实数型，指向类型表的r项），CAT域填写常量种类c。ADDR域指向常量表CONSL。
\item 填常量表CONSL：填入3.14。
\end{itemize}

(3) arr (数组类型)

\begin{itemize}
\item 填符号表SYNBL：在符号表中继续填arr的相关内容，NAME域填名字arr，TYP域指向数组的定义——类型表。
\item 填类型表TYPEL：没有数组的定义，要新增。TVAL域填类码a，TPOINT域指向数组表。
\item 填数组表ALNFL：LOW域填数组的下界1，UP域填数组的上界10，CTP域填数组元素类型itp（整数型，指向类型表的i项）。CLEN域填值单元的长度4。
\item 填符号表SYNBL：CAT域填写数组种类t（类型，可以用作定义其他变量的数据类型）。ADDR域指向长度表。
\item 填长度表CONSL：填入40。
不填活动记录VALL，因为arr是类型不是变量。
\end{itemize}

(4) $m$ (局部变量)

\begin{itemize}
\item 填符号表SYNBL：在符号表中继续填$m$的相关内容，NAME域填变量名字$m$，TYP域填itp，CAT域填写变量种类v，ADDR域填活动记录中变量的层次号（偏移量）即(3,18)。
\item 填活动记录VALL：在Display表上方填局部变量$m$，整型占4个单元，偏移量为18-21。
\end{itemize}

(5) $a$ (局部变量)

\begin{itemize}
\item 填符号表SYNBL：在符号表中继续填$a$的相关内容，NAME域填变量名字$a$，TYP域指向类型表中arr定义的数组类型a，CAT域填写变量种类v，ADDR域填活动记录中变量的层次号（偏移量）即(3,22)。
\item 填活动记录VALL：局部变量$m$上填a，数组类型占40个单元，偏移量为22-61。
\end{itemize}

(6) $I$ (局部变量)

\begin{itemize}
\item 填符号表SYNBL：在符号表中继续填$I$的相关内容，NAME域填变量名字$I$，TYP域填rtp，CAT域填写变量种类v，ADDR域填活动记录中变量的层次号（偏移量）即(3,62)。
\item 填活动记录VALL：局部变量$a$上填$I$，实型占8个单元，偏移量为62-69。
\end{itemize}

(7) F1 (函数)

\begin{itemize}
\item 填符号表SYNBL：NAME域填过程名字F1，TYP域填函数返回值类型rtp，CAT域填写函数的种类f (函数)，ADDR域指向函数表。
\item 填函数表PFINFL：LEVEL域填函数的层次号4，OFF域填区距3，FN域填函数的变量个数2，ENTRY域填函数入口物理地址Entry，PARAM域指向形参表。
\item 填形参表PARAM：根据$z$和$k$的名字、类型、种类、地址，填写NAME、TYP、CAT、ADDR四项内容。其中ADDR内容在填完VALL之后，填入变量的层次号和偏移，$z$对应(4,4)，$y$对应(4,12)。填好形参表之后，在符号表中填入变量$z$和$k$的相关信息（与形参表中内容一致）。
\item 填活动记录VALL：参数个数为2；形式单元填$z$，实型占8个单元，偏移量为4-11，填$k$，整型占4个单元，偏移量为12-15。Display表长度为5。
\end{itemize}
\end{enumerate}